/*
 * @Descripttion:
 * @version:
 * @Author: xiaozilai
 * @Date: 2022-11-17 10:10:23
 * @LastEditors: xiaozilai
 * @LastEditTime: 2022-11-17 11:40:19
 */
/*
 * @lc app=leetcode.cn id=792 lang=cpp
 *
 * [792] 匹配子序列的单词数
 *
 * https://leetcode.cn/problems/number-of-matching-subsequences/description/
 *
 * algorithms
 * Medium (47.72%)
 * Likes:    260
 * Dislikes: 0
 * Total Accepted:    18K
 * Total Submissions: 36.6K
 * Testcase Example:  '"abcde"\n["a","bb","acd","ace"]'
 *
 * 给定字符串 s 和字符串数组 words, 返回  words[i] 中是s的子序列的单词个数 。
 *
 * 字符串的 子序列 是从原始字符串中生成的新字符串，可以从中删去一些字符(可以是none)，而不改变其余字符的相对顺序。
 *
 *
 * 例如， “ace” 是 “abcde” 的子序列。
 *
 *
 *
 *
 * 示例 1:
 *
 *
 * 输入: s = "abcde", words = ["a","bb","acd","ace"]
 * 输出: 3
 * 解释: 有三个是 s 的子序列的单词: "a", "acd", "ace"。
 *
 *
 * Example 2:
 *
 *
 * 输入: s = "dsahjpjauf", words = ["ahjpjau","ja","ahbwzgqnuk","tnmlanowax"]
 * 输出: 2
 *
 *
 *
 *
 * 提示:
 *
 *
 * 1 <= s.length <= 5 * 10^4
 * 1 <= words.length <= 5000
 * 1 <= words[i].length <= 50
 * words[i]和 s 都只由小写字母组成。
 *
 * ​​​​
 */

// @lc code=start
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int numMatchingSubseq(string s, vector<string> &words) {
        vector<vector<int>> dict(26);
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            dict[s[i] - 'a'].push_back(i);
        }
        int ans = 0;
        for (auto &word : words) {
            if (isMatched(dict, word)) {
                ++ans;
                cout << "success" << endl;
            } else {
                cout << "failure" << endl;
            }
        }
        return ans;
    }

    bool isMatched(vector<vector<int>> &dict, string &word) {
        int cur_index = -1;
        for (auto &item : word) {
            int char_index = item - 'a';
            auto &ps = dict[char_index];
            auto it = upper_bound(ps.begin(), ps.end(), cur_index);
            if (it == ps.end()) {
                return false;
            } else {
                cur_index = *it;
            }
        }
        return true;
    }
};
// @lc code=end
